/**
 * 面试题11：旋转数组的最小数字
 */
public class Offer_11 {
    /**
     * 方法二：二分查找
     * <p>
     * 时间复杂度：O(logn)
     * <p>
     * 空间复杂度：O(1)
     */
    public int minArray(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("非法参数");
        }
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] > numbers[high]) {
                low = mid + 1;
            } else if (numbers[mid] < numbers[high]) {
                high = mid;
            } else {
                high--;
            }
        }
        return numbers[low];
    }

    /**
     * 方法一：线性扫描
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int minArray1(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("非法参数");
        }
        int ans = numbers[0];
        for (int num : numbers) {
            ans = (num < ans) ? num : ans;
        }
        return ans;
    }

    public static void main(String[] args) {
        Offer_11 solution = new Offer_11();
        int[] nums = { 3, 4, 5, 1, 2 };
        int ans = solution.minArray(nums);
        System.out.println(ans);
    }
}
